/*
 * All Rights Reserved.
 *
 * Author : Madhur Raj
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include "structs.h"
#include "readfile.h"

/* Forward declarations */
extern void readfile();

Node *front, *tail;
int* arr[MAXVAL];
static int count;

/* List Utility */
Node* getListNode ()
{
   Node *newNode = (Node*)malloc(sizeof(Node));
   if (front == NULL)
   {
      front = tail = newNode;
      newNode->next = newNode->prev = NULL;
   }
   else
   {
      tail->next = newNode;
      newNode->prev = tail;
      tail = newNode;
   }

   return (newNode);
}

int* getNode()
{
   Node *newNode = getListNode();

   arr[count++] = &(newNode->data);

   return (&(newNode->data));
}

void printNodes()
{
   Node *tmp = front;

   while(tmp)
   {
      printf("%d\n", tmp->data);
      tmp = tmp->next;
   }
}


void printResult()
{
   FILE *fp;
   Node *tmp;

   fp = fopen("output.txt", "w+");
   if (!fp)
   {
      printf("Unable to open file\n");
      exit(0);
   }

   tmp = front;
   while (tmp)
   {
      fprintf(fp, "%d ", tmp->data);
      tmp = tmp->next;
   }
   fclose(fp);
}
/* Endo List Utitlity */

void shellSort()
{
   int i, j;
   int shell = 5;
   while (shell>0)
   {
      for(i=0; i<(count)/shell; i++)
      {
         for(j=0; j<count; j+=shell)
         {
            if (j+i+shell < count)
            {
               if (*arr[j+i] > *arr[j+i+shell])
               {
                  SWAP(arr[j+i], arr[j+i+shell])
               }
            }
         }
      }
      shell -=2;
   }
}

void shellSortRev()
{
   int i, j;
   int shell = 5;
   while (shell>0)
   {
      for(i=0; i<(count)/shell; i++)
      {
         for(j=0; j<count; j+=shell)
         {
            if (j+i+shell < count)
            {
               if (*arr[j+i] < *arr[j+i+shell])
               {
                  SWAP(arr[j+i], arr[j+i+shell])
               }
            }
         }
      }
      shell -=2;
   }
}



int main()
{
   struct timeval start, finish;
   int count = COUNT;
   front = tail = NULL;
   readfile();
   gettimeofday(&start, NULL);
   do
   {
      shellSort();
      shellSortRev();
   } while(--count);
   gettimeofday(&finish, NULL);
   printTime(&start, & finish);
    
   printResult();
#ifdef DEBUG
   printNodes();
#endif
   return(0);
}
